import java.util.Arrays;

/**
 * 归并排序
 *
 * @Author: wanqian
 * @Date: 2021/2/3 0:53
 */
public class MergeSort {

    public static int[] arr = {42, 12, 50, 99, 50, 34, 21, 50, 66};
    private static int count = 0;


    public static void main(String[] args) {
//        int[] arr = new int[1000000];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random() * 1000);
//        }
        System.out.println(String.format("归并排序前： %s", Arrays.toString(arr)));
        long start = System.currentTimeMillis();

        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);

        long end = System.currentTimeMillis();
        long consume = (end - start);
        System.out.println("耗时" + consume + "毫秒");
        System.out.println(String.format("归并排序后： %s", Arrays.toString(temp)));
    }

    /**
     * 归并排序
     *
     * @param arr
     * @param left
     * @param right
     * @param temp
     */
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (right + left) / 2;
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);

            int l = left;
            int r = mid + 1;
            int index = left;
            while (l <= mid && r <= right) {
                if (arr[l] < arr[r]) {
                    temp[index++] = arr[l++];
                } else {
                    temp[index++] = arr[r++];
                }
            }

            while (l <= mid) {
                temp[index++] = arr[l++];
            }

            while (r <= right) {
                temp[index++] = arr[r++];
            }

            index = left;
            while (left <= right) {
                arr[left++] = temp[index++];
            }
        }
    }
}
